package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 51. N 皇后
 *
 * @author fy
 * @date 2022/3/28 11:56
 */
public class Solution51 {

    List<List<String>> res = new ArrayList<>();
    // 列占用记录
    private boolean[] col;
    // 左斜对角线占用记录
    private boolean[] leftTra;
    // 右斜对角线占用记录
    private boolean[] rightTra;

    public List<List<String>> solveNQueens(int n) {
        res.clear();
        // 初始化占用为false
        col = new boolean[n];
        for (int i = 0; i < n; i++) {
            col[i] = false;
        }
        leftTra = new boolean[2 * n - 1];
        rightTra = new boolean[2 * n - 1];
        for (int i = 0; i < 2 * n - 1; i++) {
            leftTra[i] = false;
            rightTra[i] = false;
        }
        List<Integer> set = new ArrayList<>();
        putQ(n, 0, set);
        return this.res;
    }

    /**
     * 摆放n皇后的第row行(起始位置为0)的皇后, 前面行已经摆放的列位置放置在set中
     *
     * @param n
     * @param row
     * @param set
     */
    private void putQ(int n, int row, List<Integer> set) {

        if (row == n) {
            this.res.add(genQ(n, set));
            return;
        }

        // 摆在第几列
        for (int i = 0; i < n; i++) {
            if (!col[i] && !leftTra[row + i] && !rightTra[row - i + n - 1]) {
                set.add(i);
                col[i] = true;
                leftTra[row + i] = true;
                rightTra[row - i + n - 1] = true;
                putQ(n, row + 1, set);
                rightTra[row - i + n - 1] = false;
                leftTra[row + i] = false;
                col[i] = false;
                set.remove(Integer.valueOf(i));
            }
        }
    }

    private List<String> genQ(int n, List<Integer> set) {
        List<String> qList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            qList.add(genRow(n, set.get(i)));
        }
        return qList;
    }

    private String genRow(int n, int qIndex) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i == qIndex) {
                sb.append('Q');
            } else {
                sb.append('.');
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        int n = 8;
        System.out.println(new Solution51().solveNQueens(n));
    }
}
